package a00_LeetCode.Tree;

import java.util.*;

/**
 * @Author quan
 * @Description 后序遍历
 * @Date 2023/3/28 10:18
 */
public class Num145_postOrder {
    /*public List<Integer> postorderTraversal(TreeNode root) {
        //栈和集合的创建
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        //边界
        if(root == null){
            return result;
        }
        //先不断的访问左子树:// 当前即将要访问的节点
        TreeNode cur = root;
        //定义一个引用prev，用来标记当前右子树是否已经被走过 // 上一个完全访问结束的节点
        TreeNode prev =null;
        while (cur != null || !stack.isEmpty()) {
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            //左子树访问结束，出栈：出的既是左子树又是根节点
            cur = stack.pop();
            //如果出栈的这个节点的右子树是空，或者已经被访问过，就可以直接出
            if(cur.right == null || prev == cur.right){
                // 右子树为空或者已经访问结束
                result.add(cur.val);
                // 更新prev为当前节点
                prev = cur;
                // 将cur置空，下一次循环从栈顶取元素
                cur = null;
            }else{//否则 将出栈的根节点重新入栈，先走右子树
                stack.push(cur);
                cur = cur.right;
            }
        }
        return result;
    }*/
    /**
     * 另一种思路：后序遍历的结果是左右中，前序的结果是中左右，我们将前序遍历的顺序调整一下，
     * 调整为：中右左，然后再将结果反转：即可得到左右中的输出，正好是后续遍历的结果。
     */
    public List<Integer> postorderTraversal(TreeNode root){
        //栈和集合的创建
        Deque<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        //边界
        if(root == null){
            return result;
        }
        //处理根节点
        stack.push(root);
        //调整前序的顺序：根右左:左先入栈，后右入栈
        while (!stack.isEmpty()){
            //每次弹出栈顶元素，都将该值添加到集合中，同时让该节点的右节点和左节点入栈
            TreeNode node = stack.pop();
            result.add(node.val);
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}
